package com.datastructure.test.middlelistnode;

public class MiddleListNode {

    public static void main(String[] args) {

    }

    public ListNode middleNode (ListNode head) {
        // write code here
        int length = getLengthFromListNode(head);
        int mid = 0;
        ListNode cur = head;
        while (mid<(length/2)){
            cur=cur.next;
            mid++;
        }
        return cur;
    }

    private int getLengthFromListNode(ListNode head) {
        int sum = 0;
        while (head!=null){
            sum++;
            head=head.next;
        }
        return sum;
    }

    public ListNode middleNode1 (ListNode head) {
        // write code here
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}

class ListNode {
   int val;
   ListNode next = null;
   public ListNode(int val) {
     this.val = val;
   }
 }
